package com.zjsru.oneDay202203;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @Author: likew
 * @Date: 2022/3/17
 *
 * 词典中最长的单词
 * 若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。
 *
 * 输入：words = ["w","wo","wor","worl", "world"]
 * 输出："world"
 * 解释： 单词"world"可由"w", "wo", "wor", 和 "worl"逐步添加一个字母组成。
 *
 * 输入：words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
 * 输出："apple"
 * 解释："apply" 和 "apple" 都能由词典中的单词组成。但是 "apple" 的字典序小于 "apply"
 *
 */
public class longestWord {
    public String longestWord(String[] words) {
        String ans = "";
        Set<String> set = new HashSet<>();
        for (String s : words) {
            set.add(s);
        }
        for (String s: set) {
            int n = s.length(),m = ans.length();
            if(n < m) continue;
            if (n == m && s.compareTo(ans)>0) continue;
            boolean ok = true;
            for (int i = 1; i <= n && ok ; i++) {
                String sub = s.substring(0,i);
                if(!set.contains(sub)){
                    ok = false;
                }
            }
            if(ok) ans = s;
        }
        return ans;
    }
    
    public static void main(String[] args) {
        longestWord longestWord = new longestWord();
        String[] words = new String[]{"w","wo","wor","worl", "world"};
        System.out.println(longestWord.longestWord(words));
    }

}
